package com.yuan.algorithms.arithmetic_1;

/*
ABEFGCDH
EBFGACHD
E G F B H D C A

ABDECFG
DBEAFCG
D E B F G C A
 */
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class 二叉树_用前序中序遍历求后序遍历 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String a = sc.next();
			String b = sc.next();
			BinTreeNode t = restore(a, b);
			postorderTraversal(t);
			System.out.println();
			tierErgodic(t);
		}
	}

	/**
	 * 打印树的层次遍历
	 * @param t
	 */
	private static void tierErgodic(BinTreeNode t) {
		Queue<BinTreeNode> queue = new LinkedList<BinTreeNode>();
		queue.add(t);
		while(!queue.isEmpty()) {
			BinTreeNode temp = queue.poll();
			System.out.print(temp.getData()+" ");
			if (temp.hasLChild()) {
				queue.add(temp.getLChild());
			}
			if (temp.hasRChild()) {
				queue.add(temp.getRChild());
			}
		}
	}

	/**
	 * 用前序中序遍历还原二叉树
	 * 
	 * @param a
	 *            前序遍历
	 * @param b
	 *            中序遍历
	 */
	public static BinTreeNode restore(String a, String b) {
		//递归出口，已建立完当前子树，返回上层
		if (a.equals("")) {
			return null;
		}
		char root = a.charAt(0);// 取得根节点
		BinTreeNode tree = new BinTreeNode(root);// 创建当前根节点
		
		//if(a.length()==1) return tree;
		
		int k = b.indexOf(root);
		String qxL = a.substring(1, k+1);//前序左子树
		String zxL = b.substring(0, k);//中序左子树
		
		String qxR = a.substring(k+1);//前序右子树
		String zxR = b.substring(k+1);//中序右子树
		
		tree.setLChild(restore(qxL,zxL));// 左子树
		tree.setRChild(restore(qxR,zxR));// 右子树
		return tree;
	}
	
	/**
	 * 递归遍历树，输出树的后序遍历
	 * @param tree
	 */
	public static void postorderTraversal(BinTreeNode tree){
		if(tree!=null){
			postorderTraversal(tree.getLChild());
			postorderTraversal(tree.getRChild());
			System.out.print(tree.getData()+" ");
		}
	}
	
	
}
